package DP

/**
 *
给一个正整数 n, 找到若干个完全平方数(比如1, 4, 9, ... )使得他们的和等于 n。你需要让平方数的个数最少。
给出 n = 12, 返回 3 因为 12 = 4 + 4 + 4。
给出 n = 13, 返回 2 因为 13 = 4 + 9。
 */
fun main(args: Array<String>) {
    println(miniNum(13))
}


fun miniNum(n: Int): Int {
    val result = Array(n + 1, { 0 })
    result[0] = 0
    for (i in 1 until result.size) {
        var mini = i
        for (j in 1 until result.size) {
            if (j * j <= i) {
                val temp = result[i - j * j] + 1
                result[i] = Math.min(temp, mini)
            } else break
        }
    }
    return result[n]
}
